package com.yequan.leetcode.sort;

/**
 * @author : Administrator
 * @date : 2020/6/27
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] datas = new int[]{50, 10, 90, 30, 70, 40, 80, 60, 20};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(datas, 0, datas.length - 1);
        for (int data : datas) {
            System.out.println(data);
        }
    }

    /**
     * 1.找出基准数,一般为第一个
     * 2.以基准数为准,对基准数左右的子数组进行快排
     *
     * @param data
     * @param left
     * @param right
     * @return
     */
    public void quickSort(int[] data, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(data, left, right);
            quickSort(data, left, pivotIndex - 1);
            quickSort(data, pivotIndex + 1, right);
        }
    }

    /**
     * 找出基准数
     *
     * @param data
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] data, int left, int right) {
        int pivot = data[left];
        int i = left;
        int j = right;
        while (i != j) {
            while (data[j] > pivot && i < j) {
                j--;
            }
            while (data[i] <= pivot && i < j) {
                i++;
            }
            if (i < j) {
                swap(data, i, j);
            }
        }
        data[left] = data[j];
        data[j] = pivot;
        return j;
    }

    /**
     * 交换左右数据
     *
     * @param data
     * @param i
     * @param j
     */
    private void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

}
